﻿namespace KinonekoSoftware.Extensions.Collections.BST
{
    partial class BinaryTreeCollection<TKey, TValue>
    {
        
        public bool Remove(TKey key)
        {
            if (key is null)
            {
                return false;
            }

            if (Root is null)
            {
                return false;
            }

            if (EqualityComparer<TKey>.Default.Equals(Root.Key, key))
            {
                Root = null;
                _count--;
                _version++;
                return true;
            }

            return RemoveImpl(Root, key);
        }
        
        public bool Remove(TValue content)
        {
            if (content is null)
            {
                return false;
            }

            if (Root is null)
            {
                return false;
            }

            if (EqualityComparer<TKey>.Default.Equals(Root.Key, _selector( content)))
            {
                Root = null;
                _count--;
                _version++;
                return true;
            }

            return RemoveImpl(Root, _selector( content));
        }

        protected bool RemoveImpl(Node current, TKey value, bool rebalance = true)
        {
            if (current is null)
            {
                return false;
            }

            var result = Comparer<TKey>.Default.Compare(current.Key, value);

            //
            // 值相等，删除当前
            if (result == 0)
            {
                //
                //
                var parent = current.Parent;

                if (ReferenceEquals(parent.Left, current))
                {
                    RemoveLeft(parent, current);
                }
                else
                {
                    RemoveRight(parent, current);
                }


                if (rebalance)
                {
                    current.Rebalance();
                }

                _version++;
                _count--;
                return true;
            }

            if (result < 0)
            {
                RemoveImpl(current.Right, value, rebalance);

            }
            else
            {
                RemoveImpl(current.Left, value, rebalance);
            }


            return false;
        }

        private static void RemoveLeft(Node parent, Node current)
        {
            //
            // 叶子节点，直接删除
            if (current.IsLeaf)
            {
                parent.Left = null;
                return;
            }

            //
            // 左节点为空，把左节点的值复制到当前节点，删除左节点
            if (current.Right is null)
            {
                current.Key   = current.Left.Key;
                current.Value = current.Left.Value;
                current.Left  = null;
                return;
            }

            //
            // 右节点为空，把右节点的值复制到当前节点，删除右节点
            if (current.Left is null)
            {
                current.Key   = current.Right.Key;
                current.Value = current.Right.Value;
                current.Right = null;
                return;
            }


            var pred        = current.Successor;
            var pred_parent = pred.Parent;

            //
            //
            pred_parent.Left = pred.Right;
            pred.Left        = current.Left;
        }

        private static void RemoveRight(Node parent, Node current)
        {
            if (current.IsLeaf)
            {
                parent.Right = null;
                return;
            }

            //
            // 左节点为空，把左节点的值复制到当前节点，删除左节点
            if (current.Left is null)
            {
                current.Key   = current.Right.Key;
                current.Value = current.Right.Value;
                current.Right = null;
                return;
            }

            //
            // 右节点为空，把右节点的值复制到当前节点，删除右节点
            if (current.Right is null)
            {
                current.Key   = current.Left.Key;
                current.Value = current.Left.Value;
                current.Left  = null;
                return;
            }

            var pred        = current.Successor;
            var pred_parent = pred.Parent;

            //
            //
            pred_parent.Left = pred.Right;
            pred.Left        = current.Left;
        }

        
        public void Clear()
        {
            Root  = null;
            _count = 0;
            _version++;
        }
    }
}